package org.sanguine.study.hometasks.second;

import java.util.Comparator;
import java.util.HashSet;
import java.util.NavigableMap;
import java.util.NavigableSet;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.TreeSet;

import org.sanguine.study.hometasks.second.auxiliary.Segment;

public class Task17 {
	private NavigableMap<Double[], Segment> pointsSet;
	private NavigableSet<Segment> sweepLineStatus;
	private SortedMap<Double, Set<Segment>> intersections;
	
	public void addSegment(Segment segment) {
		pointsSet.put(segment.leftEnd(), segment);
		pointsSet.put(segment.rightEnd(), segment);
	}
	
	public Task17() {
		pointsSet = new TreeMap<>(new Comparator<Double[]>(){

			@Override
			public int compare(Double[] o1, Double[] o2) {
				if (o1[0] != o2[0]) return o1[0].compareTo(o2[0]); //more left point less than more right
				else if (o1[2] == o2[2]) return o1[1].compareTo(o2[1]); //for same end's points lower point less than higher point
				else return (o1[2] == 0.0) ? -1 : 1; //at last left point of segment always less than right point of segment
			}
			
		});
		
		sweepLineStatus = new TreeSet<>(); //using natural order of segments. compare by y of left end, if this.y > o.y that o1 above o2
		intersections = new TreeMap<>();
	}
	
	/**
	 * Find the leftmost intersection in segments' set (added early by addSegment method)  
	 * @return array of Double {x, y} or null if no one intersection found
	 * Using modified algorithm Shamos-Hoye 1976   
	 */
	
	public Double[] findLeftmostIntersection() {
		
		if (pointsSet.size() <= 2) return null; //only one segment or nothing
		
		intersections.clear();
		sweepLineStatus.clear();
		
		for (Double[] point : pointsSet.keySet()) {
			if (!intersections.isEmpty() && intersections.firstKey() <= point[0]) break; //minimum x of intersection found
			
			if (point[2] == 0.0) {
				Segment s = pointsSet.get(point);
				sweepLineStatus.add(s);
				Segment above = sweepLineStatus.higher(s);
				if (above != null && above.isCrossed(s)) {
					addIntersection(above, s);
					continue;
				}
				Segment below = sweepLineStatus.lower(s);
				if (below != null && below.isCrossed(s)) addIntersection(below, s);
			} else {
				Segment s = pointsSet.get(point);
				Segment above = sweepLineStatus.higher(s);
				Segment below = sweepLineStatus.lower(s);
				if (above != null && below != null && above.isCrossed(below)) addIntersection(above, below);
				sweepLineStatus.remove(s);
			}
		}

		if (!intersections.isEmpty()) {
			Segment[] segments = intersections.get(intersections.firstKey()).toArray(new Segment[0]);
			return segments[0].crossingPoint(segments[1]);
		} else return null;
	}

	private void addIntersection(Segment s1, Segment s2) {
		Double[] crossing = s1.crossingPoint(s2);
		
		if (crossing != null) {
			Set<Segment> listSegments = intersections.get(crossing[0]);
			if (listSegments == null) listSegments =  new HashSet<>();
			listSegments.add(s1);
			listSegments.add(s2);
			intersections.put(crossing[0], listSegments);
		}
	}
	
}
